1. Field of the Invention
The present invention relates to an apparatus for embodying the AntNet algorithm that applies ecosystem colony characteristics to network environments in hardware. The apparatus according to the present invention can be constructed as a system-on-chip (SoC) system.
2. Related Prior Art
Most existing network techniques are based on high-performance apparatuses and experienced managers. Thus, network design and maintenance costs are rapidly increasing to meet the requirements of continuously increasing network size and traffic. Recently, there have been explored a variety of methods for effectively managing rapid traffic processing and communication networks and, simultaneously, minimizing infrastructure construction costs by reusing existing equipment to cope with incessantly evolving network techniques. Among the methods, a method of applying various behavior patterns of social insects that form a colony to actual situations is recognized as an excellent and effective method.
Colony characteristics of insects can be simply defined as a collective behavior of individuals. Individual objects organize a group and carry out complicated tasks such as making a nest or seeking for food. Although each individual carries out a small task, small efforts are collected to address large and complicated problems.
To analyze the behavior pattern of ants that form a colony and have the largest number of individuals on the earth and apply the behavior pattern to actual various situations to find an optimized method is the ant colony optimization (ACO) theory [M. Dorigo, G, Di Caro and L. M. Gambardella, “Ant Algorithm for Discrete Optimization,” Artificial Life, Vol. 5, No. 3, pp. 137-172, 1999; E. bonabeau, M. Dorigo and G. Theraulaz, “Inspiration for Optimization from Social Insect Behavior,” Nature, Vol. 406, pp. 39-42, July 2000]. According to the ACO theory, there was proposed a successful approach to a problem such as the “Traveling Salesman Problem”, which models foraging using pheromones among various characteristics of the ant [M. Dorigo, V. Maniezzo, and A. Colorni, “The Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Trans. on Systems, Man and Cybernetics-Part B, Vol. 26, No. 1, pp. 1-13, 1996; M. Dorigo and L. M. Gambardella, “AntColony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Trans. on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, April 1997].
A communication network is an application field to which the ACO theory has been successfully applied so far because the ant's behavior pattern can be nearly completely applied to the actual network environment by modeling a network node and traffic as an ant nest and ants, respectively. Accordingly, the network environment to which the ACO mechanism is applied has characteristics including adaptability and stability for unpredictable situations and distributed processing capability through a self-organization function, which are features required for next-generation networks. Schoonderwored proposed a routing and load balancing technique in line switching networks using the ACO [R. Schoonderwored, O. Holland, J. Bruten, and L. Rothkrantz, “Ant-based Load Balancing in Telecommunications networks,” Adaptive Behavior, Vol. 5, No. 2, pp. 169-207, 1996], and Di Caro and Dorigo developed an adaptive routing technique called AntNet [G. Di Caro and M. Dorigo, “AntNet: Distributed Stigmergetic control for Communications Networks,” Journal of Artificial Intelligence Research 9, pp. 317-365, December 1998].
“AntNet” is an algorithm of choosing a relatively satisfactory route for a mobile agent defined as an “Ant” in variable network environments. Here, the “Ant” is a network packet that models the foraging habit of the ant colony. The foraging habit of the ant finds food and secretes pheromones along a route through which an ant has moved to reach the position where the food was found, to make other ants move to the place where the pheromones have been secreted. In this manner, an optimized route through which lots of ants are moved is naturally provided. The AntNet collects various routes and relatively appraises each route using Ant packets. Each node forwards general network data along a relatively satisfactory network route based on the appraised result.
The basic concept of the AntNet will now be explained.
The AntNet uses an agent packet called Ant in order to investigate a network environment. The types of Ant include a forward Ant and a Backward Ant. The forward Ant has the same priority as that of general network data and stores routing information in each node while moving from an initially generated node to a destination mode. The forward Ant becomes a backward Ant when it arrives at the destination. The backward Ant provides information about an optimum route for the general network data using the routing information stored in each node while returning the way the forward Ant has come. Each node has two kinds of storage places for storing the routing information. One of the storage places is a local traffic model that stores statistical data about network states and the other one is a routing table that stores routing preferences for the next nodes that should be passed through to move from a current node to a specific destination node. The preferences are represented by a normalized probability from 0 to 1. The sum of the next node preferences for destination nodes is 1. The higher the preference of a node becomes, the higher the probability becomes that an Ant will select the node in order to go to a corresponding destination node. A next node is finally decided upon with reference to the relative preference of the node and the length of an output queue that should be passed in order to go to the next node. Assume that P'nd is the probability of selecting a next node n in order to reach a destination node d. The P'nd is decided as the sum of the preference Pnd for the next node n, stored in a routing table, and the length In of the output queue that must be passed to reach the next node n. The In is a prior value and decides a weight. When |N| is the total number of next nodes connected to the current node, the P'nd can be represented as follows.
                                          P            ′                    ⁢          nd                =                              Pnd            +                          α              ⁢                                                          ⁢              ln                                            1            ⁢                                                                          α                  (                                      ❘                    N                                                                    -                1                            )                                                          [                  Equation          ⁢                                          ⁢          1                ]            
The preferences stored in the routing tables are updated by the backward Ant. The range of updating the preferences is decided by a reinforcement value r. The reinforcement value is a parameter that represents the relative speed of routing information. The reinforcement value r is represented as follows.
                    r        =                                            C              1                        ⁡                          (                              Wbest                T                            )                                +                                    C              2                        ⁡                          (                                                Isup                  -                  Iinf                                                                      (                                          Isup                      -                      Iinf                                        )                                    +                                      (                                          T                      -                      Iinf                                        )                                                              )                                                          [                  Equation          ⁢                                          ⁢          2                ]            
Here, Wbest represents the shortest routing time within an effective interval required for the forward Ant to move from a source node to a destination node and T denotes the current routing time. Isup and Iinf are approximated parameters representing the reliability of the average routing time, and C1 and C2 represent weights.
The definition of the reinforcement value is important to improve the performance of the AntNet. To properly appraise the relative quality of routing information, a method of varying the reinforcement is needed. A lot of methods for deciding an optimum reinforcement value have been proposed [M. Dorigo, M. Zlochin, N. Meuleau, and M. Birattari, “Updating ACO Pheromones using Stochastic Gradient Ascent and Cross-Entropy Methods]. Routing table values of the current node are updated using the reinforcement value obtained by Equation 2 as follows:Pfd←Pft+r(1−Pfd)  [Equation 3]Pnd←Pnd−rPndr ∈ (0,1), n, f ∈ N, n≠f
Here, the reinforcement value r is larger than 0 but smaller than 1, and N is a set of all next nodes connected to the current node. In addition, f represents a next node through which the current Ant has passed to reach the destination node and n denotes other next nodes. Pfd is the routing preference when the Ant passes through the next node f to arrive at the destination node and Pnd is the preference when the Ant reaches the destination node using other next nodes. Referring to Equation 3, routing preference for the next node f is increased in proportion to the reinforcement value and routing preferences with respect to the other next nodes are decreased in proportion to the reinforcement value. In this way, a next node that has been frequently selected for previous Ants to travel and has excellent routing quality is selected as the next route.
Experimental results showing that the AntNet is superior to existing various adaptive routing techniques have been frequently published [G. Di Caro and M. Dorigo, “AntNet: Distributed stigmergetic Control for Communications Networks,” Journal of Artificial Intelligence Research 9, pp. 317-365, December 1998; K. M. Sim and W. H. Sun, “Multiple Ant-Colony Optimization for Network Routing,” Proc. of the First International Symposium on Cyber Worlds, pp. 277-281, November 2002; Y. Yang, A. N. Zincir-Heywood, M. I. Heywood, and S. Srinivas, “Agent-Based Routing Algorithms on a LAN,” Proc. of the IEEE Canadian Conference on Electrical & Computer Eng., Vol. 3, pp. 1442-1447, May 2002]. However, the performance of AntNet is decided by the accuracy of network information obtained from Ant packets and thus it is important to increase the accuracy of the information for actual application of the AntNet.
The most important item of network information collected by the AntNet is routing time. To improve accuracy of the routing time, the Ant packet processing time at each node is minimized such that only information about routing time between nodes is included in the routing time. Furthermore, it is important to make Ant packet processing speeds at each node uniform to reduce an error in measuring the routing time. Moreover, it is also important to rapidly apply the routing time information to maximize general packet throughput. Accordingly, Ant packets are processed in a hardware manner by a packet processing device to minimize the processing speed and time. The routing time information is updated in the same manner to maximize its effect.
However, a conventional packet processing device such as a commercial network processor has a relatively simple computation unit because it is designed based on general network data, and processes complicated calculations in a software manner using a processor included therein. Although the Ant packet is sensitive to a processing speed, a relatively large amount of calculations and a separate computation unit are required for processing Ant information. Accordingly, it is effective to design an Ant processor using a separate logic only for Ant processing rather than using command-level general hardware.